package com.zp.self.module.level_4_算法练习.算法.排序;

import java.util.Arrays;

/**
 * @author By ZengPeng
 */
public class 鸡尾酒排序_O_nXn_logn {
    //测试
    public static void main(String[] args) {
        int[] ints = {7, 1, 5, 3, 6, 4};
        new 鸡尾酒排序_O_nXn_logn().cocktailSort(ints);
        System.out.println(Arrays.toString(ints));
    }

    /**
     鸡尾酒排序 ： 钟摆一样排序，先向左比较大小 ，记录是否有交换过？ 说明还是无序的：有序 breake
                    再向右比较，...
             优势：在大部分数据都有序的情况下，能减少排序次数
             案例：在一个有序数组中，插入一个新的数.
                 1.二分法找到要插入的下标 O(log n)
                 2.鸡尾酒排序 O(n) : 插入到数组头部，向左比较一次即可。
     */
    private static void cocktailSort(int[] arr) {
        //一个来回找到最大值，最小值
        for (int i = 0; i < arr.length/2; i++) {
            boolean isOk = true;
            for (int j = i; j < arr.length-1-i; j++) { //向右比较，j的范围 [i ,arr.length-1 -i ]
                isOk = isOk(arr, isOk, j);
            }
            if(isOk)
                return;
            else
                isOk=true;
            for (int j = arr.length-2-i; j >i; j--) { //向左比较 ，j的范围 [i +1,arr.length-1 -i ]
                isOk = isOk(arr, isOk, j);
            }
            if(isOk)
                return;
        }
    }

    private static boolean isOk(int[] arr, boolean isOk, int j) {
        if(arr[j]> arr[j+1]){
            arr[j] =  arr[j]^arr[j+1];
            arr[j+1] =  arr[j]^arr[j+1];
            arr[j] =  arr[j]^arr[j+1];
            isOk =false;
        }
        return isOk;
    }
}
